//
// Created by zx208 on 2024/10/16.
//

// 求设计一算法完成用最少时间在表中查找数值为x的元素，
// 若找到则将其与后继元素位置相交换；
// 若找不到则将其插人表中并使表中元素仍递增有序。

#include "../SequenceList.h"

Status Find_Or_Insert_SL(SqList *L, ElemType x){
    // 对于有序数组来说 最快查找就是二分查找
    int left = 0, right = L->length - 1, mid, temp;
    while(left <= right){
        mid = (left + right) / 2;
        if(L->elem[mid] == x) break;
        if(L->elem[mid] > x) right = mid - 1;
        else left = mid + 1;
    }

    // 交换或插入
    if(L->elem[mid] == x && mid != L->length - 1){
        temp = L->elem[mid];
        L->elem[mid] = L->elem[mid+1];
        L->elem[mid+1] = temp;
    } else{
        // 要找到元素应该插入表中位置
        // 1：直接遍历比较
//        for (int i = 0; i < L->length; i++) {
//            if(L->elem[i] > x){
//                for (int j = L->length-1; j >= i; --j) {
//                    L->elem[j+1] = L->elem[j];
//                }
//                L->elem[i] = x;
//                L->length++;
//                break;
//            }
//        }
        // 2：使用二分查找的right
        for (int i = L->length-1; i > right; --i) L->elem[i+1] = L->elem[i];
        L->elem[right+1] = x;
        L->length++;
    }
    return OK;
}

int main(void){
    SqList L;
    int a[] = {3,4,6,7, 0};
    L.elem = a;
    L.length = sizeof a / sizeof( int) - 1;
    ElemType e = 5;
    Find_Or_Insert_SL(&L, e);
    for (int i = 0; i < L.length; ++i) {
        printf("%d ", L.elem[i]);
    }
    return 0;
}